#include "my_slru_cache.h"

typedef struct {
    my_rbtree_node_t                tree_node;
    int                             idx;
    int64_t                         key_len;
    my_buf_chain_t                  *data;
    my_queue_t                      queue;
    char                            key[0];
} my_slru_cache_item_t;

static my_slru_cache_item_t *
my_slru_cache_item_create(my_cache_key_t *key, my_buf_chain_t *data) {
    int64_t key_len = key->key_len;
    my_slru_cache_item_t *item = my_malloc(sizeof(my_slru_cache_item_t) + key_len);
    bzero(item, sizeof(my_slru_cache_item_t));
    item->tree_node.key = key->digest32;
    item->key_len = key->key_len;
    memcpy(item->key, key->key, key_len);
    item->data = my_buf_chain_alloc();
    my_buf_chain_copy_all(item->data, data);
    return item;
}

static void
my_slru_cache_item_free(my_slru_cache_item_t *item) {
    my_buf_chain_free(item->data);
    my_free(item);
}

static inline int
my_slru_cache_item_cmp(my_slru_cache_item_t *a, my_slru_cache_item_t *b) {
    if (a->tree_node.key != b->tree_node.key) {
        return (a->tree_node.key < b->tree_node.key) ? -1 : 1;
    } else if (a->key_len != b->key_len) {
        return (a->key_len < b->key_len) ? -1 : 1;
    }

    return memcmp(a->key, b->key, a->key_len);
}

static inline int
my_slru_cache_item_cmp_1(my_slru_cache_item_t *a, my_cache_key_t *key) {
    if (a->tree_node.key != key->digest32) {
        return (a->tree_node.key < key->digest32) ? -1 : 1;
    } else if (a->key_len != key->key_len) {
        return (a->key_len < key->key_len) ? -1 : 1;
    }

    return memcmp(a->key, key->key, a->key_len);
}

static void
my_slru_cache_rbtree_insert_value(my_rbtree_node_t *temp, my_rbtree_node_t *node,
    my_rbtree_node_t *sentinel) {

    my_rbtree_node_t **p;
    my_slru_cache_item_t *n, *t;

    for (; ;) {
        n = (my_slru_cache_item_t *)node;
        t = (my_slru_cache_item_t *)temp;

        // do not process the same key
        if (my_slru_cache_item_cmp(n, t) < 0) {
            p = &temp->left;
        } else {
            p = &temp->right;
        }

        if (*p == sentinel) {
            break;
        }

        temp = *p;
    }

    *p = node;
    node->parent = temp;
    node->left = sentinel;
    node->right = sentinel;
    my_rbt_red(node);
}

static my_slru_cache_item_t *
my_slru_cache_rbtree_lookup(my_rbtree_t *rbtree, my_cache_key_t *key) {
    int rc;
    my_slru_cache_item_t *n;
    my_rbtree_node_t  *node, *sentinel;

    node = rbtree->root;
    sentinel = rbtree->sentinel;

    while(node != sentinel) {
        n = (my_slru_cache_item_t *)node;
        rc = my_slru_cache_item_cmp_1(n, key);

        if (rc < 0) {
            node = node->right;
            continue;
        }

        if (rc > 0) {
            node = node->left;
            continue;
        }

        return n;
    }

    return NULL;
}

static my_bool_t
my_slru_cache_list_is_full(my_slru_cache_t *slru_cache, int list_idx) {
    if (slru_cache->max_item > 0 &&
        *(slru_cache->lists_n + list_idx) >= slru_cache->max_item) {
        return MY_TRUE;
    }

    if (slru_cache->max_bytes > 0 &&
        *(slru_cache->lists_bytes + list_idx) >= slru_cache->max_bytes) {
        return MY_TRUE;
    }

    return MY_FALSE;
}

void
my_slru_cache_remove_helper(my_slru_cache_t *slru_cache, my_cache_key_t *key) {
    my_slru_cache_item_t *item =
        my_slru_cache_rbtree_lookup(&slru_cache->tree, key);
    if (!item) {
        return;                 // not found
    }

    *(slru_cache->lists_n + item->idx) -= 1;
    *(slru_cache->lists_bytes + item->idx) -= my_buf_chain_total_bytes(item->data);
    my_queue_remove(&item->queue);
    my_rbtree_delete(&slru_cache->tree, &item->tree_node);
    my_slru_cache_item_free(item);
}

void
my_slru_cache_put_helper(my_slru_cache_t *slru_cache, my_cache_key_t *key,
    my_buf_chain_t *data) {
    my_slru_cache_remove_helper(slru_cache, key);
    my_slru_cache_item_t *item = my_slru_cache_item_create(key, data);

    if (my_slru_cache_list_is_full(slru_cache, 0)) {    // retire
        my_queue_t *back_q = my_queue_last(slru_cache->lists + 0);
        my_slru_cache_item_t *back_item =
            my_queue_data(back_q, my_slru_cache_item_t, queue);
        *(slru_cache->lists_n + 0) -= 1;
        *(slru_cache->lists_bytes + 0) -= my_buf_chain_total_bytes(back_item->data);
        my_queue_remove(&back_item->queue);
        my_rbtree_delete(&slru_cache->tree, &back_item->tree_node);
        my_slru_cache_item_free(back_item);
    }

    *(slru_cache->lists_n + 0) += 1;
    *(slru_cache->lists_bytes + 0) += my_buf_chain_total_bytes(item->data);
    my_rbtree_insert(&slru_cache->tree, &item->tree_node);
    my_queue_insert_head(slru_cache->lists + 0, &item->queue);
}

my_bool_t
my_slru_cache_get_helper(my_slru_cache_t *slru_cache, my_cache_key_t *key,
    my_buf_chain_t *data) {

    my_slru_cache_item_t *item =
        my_slru_cache_rbtree_lookup(&slru_cache->tree, key);
    if (!item) {
        return MY_FALSE;                // not found
    }

    // copy data.
    my_buf_chain_copy_all(data, item->data);

    // already on fainal lists? move to head
    if (item->idx == slru_cache->nlist - 1) {
        my_queue_remove(&item->queue);
        my_queue_insert_head((slru_cache->lists + item->idx), &item->queue);
        return MY_TRUE;
    }

    int64_t data_len = my_buf_chain_total_bytes(item->data);
    *(slru_cache->lists_bytes + item->idx) -= data_len;
    *(slru_cache->lists_n + item->idx) -= 1;
    my_queue_remove(&item->queue);
    item->idx += 1;

    if (!my_slru_cache_list_is_full(slru_cache, item->idx)) {
        *(slru_cache->lists_bytes + item->idx) += data_len;
        *(slru_cache->lists_n + item->idx) += 1;
        my_queue_insert_head((slru_cache->lists + item->idx), &item->queue);
        return MY_TRUE;
    }

    // current list is full, swap
    my_queue_t *back_q = my_queue_last(slru_cache->lists + item->idx);
    my_slru_cache_item_t *back_item =
        my_queue_data(back_q, my_slru_cache_item_t, queue);
    my_queue_remove(back_q);
    int64_t back_data_len = my_buf_chain_total_bytes(back_item->data);
    *(slru_cache->lists_bytes + back_item->idx) -= back_data_len;
    *(slru_cache->lists_n + back_item->idx) -= 1;
    back_item->idx -= 1;
    *(slru_cache->lists_bytes + back_item->idx) += back_data_len;
    *(slru_cache->lists_n + back_item->idx) += 1;
    my_queue_insert_head((slru_cache->lists + back_item->idx), &back_item->queue);

    *(slru_cache->lists_bytes + item->idx) += data_len;
    *(slru_cache->lists_n + item->idx) += 1;
    my_queue_insert_head((slru_cache->lists + item->idx), &item->queue);

    return MY_TRUE;
}

my_bool_t
my_slru_cache_get(my_slru_cache_t *slru_cache, my_cache_key_t *key,
    my_buf_chain_t *data) {
    my_spin_lock_lock(&slru_cache->lock);
    my_slru_cache_get_helper(slru_cache, key, data);
    my_spin_lock_unlock(&slru_cache->lock);
}

void
my_slru_cache_put(my_slru_cache_t *slru_cache, my_cache_key_t *key,
    my_buf_chain_t *data) {
    my_spin_lock_lock(&slru_cache->lock);
    my_slru_cache_put_helper(slru_cache, key, data);
    my_spin_lock_unlock(&slru_cache->lock);
}

void
my_slru_cache_remove(my_slru_cache_t *slru_cache, my_cache_key_t *key) {
    my_spin_lock_lock(&slru_cache->lock);
    my_slru_cache_remove_helper(slru_cache, key);
    my_spin_lock_unlock(&slru_cache->lock);
}


void
my_slru_cache_open(my_slru_cache_t *slru_cache, int nlists,
    int64_t max_item, int64_t max_bytes) {

    if (nlists <= 0) {
        MY_LOG_FATAL0("slru_cache", "nlist must be greater than 0");
    }

    if (max_item < 0 || max_bytes < 0) {
        MY_LOG_FATAL0("slru_cache", "invalid params");
    }

    if (max_item == 0 && max_bytes == 0) {
        MY_LOG_FATAL0("slru_cache", "max_item or max_bytes must be greater than 0");
    }

    bzero(slru_cache, sizeof(my_slru_cache_t));
    my_spin_lock_init(&slru_cache->lock);

    slru_cache->max_item = max_item / nlists;
    slru_cache->max_bytes = max_bytes / nlists;
    if(slru_cache->max_item == 0 && max_item != 0) {
        slru_cache->max_item = 1;
    }
    if (slru_cache->max_bytes == 0 && max_bytes != 0) {
        slru_cache->max_bytes = 1;
    }

    my_queue_t *lists = my_malloc(sizeof(my_queue_t) * nlists);
    for (int i = 0; i < nlists; i++) {
        my_queue_init(lists + i);
    }

    int64_t *lists_bytes = my_malloc(sizeof(int64_t) * nlists);
    bzero(lists_bytes, sizeof(int64_t) * nlists);

    int64_t *lists_n = my_malloc(sizeof(int64_t) * nlists);
    bzero(lists_n, sizeof(int64_t) * nlists);

    slru_cache->nlist = nlists;
    slru_cache->lists = lists;
    slru_cache->lists_bytes = lists_bytes;
    slru_cache->lists_n = lists_n;

    my_rbtree_init(&slru_cache->tree, &slru_cache->sentinel,
        my_slru_cache_rbtree_insert_value);
}

void
my_slru_cache_close(my_slru_cache_t *slru_cache) {
    my_queue_t *list, *q;
    my_slru_cache_item_t *item;

    for (int i = 0; i < slru_cache->nlist; i++) {
        list = slru_cache->lists + i;
        while(!my_queue_empty(list)) {
            q = my_queue_last(list);
            my_queue_remove(q);
            item = my_queue_data(q, my_slru_cache_item_t, queue);
            my_rbtree_delete(&slru_cache->tree, &item->tree_node);
            my_slru_cache_item_free(item);
        }
    }

    my_free(slru_cache->lists_n);
    my_free(slru_cache->lists_bytes);
    my_free(slru_cache->lists);
}